export interface TreeNode {
    value: number;
    left: TreeNode | null;
    right: TreeNode | null;
}

/**
 * @description 赫夫曼树
 * @example
 * 1. 先将数组转换成节点数组
 * 2. 再节点数组按照降序排序，最小值在最后
 * 3. 取出最后一个值（最小值）作为左节点，再取出最后第二个值作为右节点
 * 4. 由上面取出的最后两个值的和作为一个父节点创建节点，再将该节点放入节点数组中
 * 5. 重复2~4，直到节点数组只剩下一个元素
 */
export default class HuffmanTree {

    private static createNode(value: number) {
        return { value, left: null, right: null };
    }

    public static transform(arr: number[]) {
        const nodes: TreeNode[] = [];
        for (const value of arr) {
            nodes.push(this.createNode(value));
        }
        while (nodes.length > 1) {
            nodes.sort((a, b) => b.value - a.value);
            const leftNode = nodes.pop() as TreeNode;
            const rightNode = nodes.pop() as TreeNode;
            const newNode = {
                value: leftNode.value + rightNode.value,
                left: leftNode,
                right: rightNode
            };
            nodes.push(newNode);
        }
        return nodes[0];
    }

    public static front(node: TreeNode | null, res: number[] = []) {
        if (node !== null) {
            res.push(node.value);
            this.front(node.left, res);
            this.front(node.right, res);
        }
        return res;
    }
}